class Solution {
public:
    unordered_map<string, vector<int>> memo;
    vector<int> diffWaysToCompute(string input) {
        dp(input);
        return memo[input];
    }
    void dp(string s) {
        if (memo.find(s) != memo.end()) return;
        memo[s] = vector<int>{};
        for(int i = 0 ; i < s.length(); i++)
        {
            if(s[i] == '+' || s[i] == '-' || s[i] == '*')
            {
                dp(s.substr(0, i));
                dp(s.substr(i + 1));
                vector<int> v1 = memo[s.substr(0, i)];
                vector<int> v2 = memo[s.substr(i + 1)];
                switch(s[i])
                {
                    case '+':
                        for(auto m : v1)
                            for(auto n : v2)
                                memo[s].push_back(m + n);
                        break;
                    case '-':
                        for(auto m : v1)
                            for(auto n : v2)
                                memo[s].push_back(m - n);
                        break;
                    case '*':
                        for(auto m : v1)
                            for(auto n : v2)
                                memo[s].push_back(m * n);
                        break;
                }
            }
        }
        if(memo[s].empty()) memo[s].push_back(stoi(s));
        return;
    }
};
